We start with a word on notation. Random variables are denoted by capital letters (e.g., X, Y) and realizations of them by lower-case letters (e.g., x, y). Random vectors are denoted by bold capital letters (e.g., X, Y) and realizations of them by bold lower-case letters (e.g., x, y). Expectation of a function f(X, Y) over both X and Y is denoted as EX,Y{f(X, Y)}. The subscript “X,Y” will be dropped when it is clear from the context.
Slepian-Wolf coding [28] concerns with near-lossless source coding with side information at the decoder. For lossless compression of a pair of correlated, discrete random variables X and Y, a rate of RX+RY=H(X, Y) is possible if they are encoded jointly [15]. However, Slepian and Wolf [28] showed that the rate RX+RY=H(X, Y) is almost sufficient even for separate encoding (with joint decoding) of X and Y. Specifically, the Slepian-Wolf theorem says that the achievable region for coding X and Y is given byRX≧H(X|Y), RY≧H(Y|X), RX+RY≧H(X,Y).  (1)This result shows that there is no loss of coding efficiency with separate encoding when compared to joint encoding as long as joint decoding is performed. When the side information (e.g., Y) is perfectly available at the decoder, then the aim of Slepian-Wolf coding is to compress X to the rate limit H(X|Y).
Wyner-Ziv coding [37], [38] deals with the problem of rate-distortion with side information at the decoder. It asks the question of how many bits are needed to encode X under the constraint that E{d(X, {circumflex over (X)})}≦D, assuming the side information Y is available at the decoder but not at the encoder. This problem generalizes the setup of [28] in that coding of X is lossy with respect to a fidelity criterion rather than lossless. For both discrete and continuous alphabets of  and general distortion metrics d(•), Wyner and Ziv [37] gave the rate-distortion function RWZ(D) for this problem as RWZ(D)=inf I(X; U|Y), where the infimum is taken over all auxiliary random variables U such that Y→X→U is a Markov chain and there exists a function {circumflex over (X)}={circumflex over (X)}(U, Y) satisfying E{d(X, {circumflex over (X)})}≦D. According to [37],
                                          R            WZ                    ⁡                      (            D            )                          ≥                              R                                          X                                            ⁢              Y                                ⁡                      (            D            )                              =                        inf                      {                                          X                ^                            ∈                                                                  ⁢                                      :                                    ⁢                  E                  ⁢                                      {                                          d                      ⁡                                              (                                                  X                          ,                                                      X                            ^                                                                          )                                                              }                                                  ≤                D                                      }                          ⁢                  I          (                      X            ;                          X              ^                                                ⁢        Y              )    ,where RX|Y(D) is the classic rate-distortion function of coding X with side information Y available at both the encoder and the decoder. Compared to coding of X when the side information Y is also available at the encoder, there is in general a rate loss with Wyner-Ziv coding. Zamir quantified this loss in [42], showing a <0.22 bit loss for binary sources with Hamming distance and a <0.5 b/s loss for continuous sources with MSE distortion.
When D is very small and the source is discrete-valued, the Wyner-Ziv problem degenerates to the Slepian-Wolf problem with RWZ(D)=RX|Y(D)=H(X|Y). Another interesting setup is the quadratic Gaussian case with the source model being X=Y+Z and Z˜N(0, σZ2), then
                    R        WZ            ⁡              (        D        )              =                            R                                    X                                      ⁢            Y                          ⁡                  (          D          )                    =                        1          2                ⁢                              log            +                    ⁡                      [                                          σ                Z                2                            D                        ]                                ,where log+ x=max{log x, 0}, i.e., there is no rate loss in this case. Note that Y is arbitrarily distributed [22]. When Y is also Gaussian, then X and Y are jointly Gaussian memoryless sources. This case is of special interest in practice because many image and video sources can be modeled as jointly Gaussian and Wyner-Ziv coding suffers no rate loss. For the sake of simplicity, we consider this specific case in our code designs.